import numpy as np

#越小越像
def dtw_distance(sequence_a, sequence_b, distance_func=lambda x,y: abs(x-y), mww: int=100000):
    """Computes dtw distance between two time series
        
        Args:
            ts_a: time series a
            ts_b: time series b
            d: distance function
            mww: max warping window, int, optional (default = infinity)
            
        Returns:
            dtw distance
        """

    #  Create cost matrix via broadcasting with large int
    sequence_a ,sequence_b =np.array(sequence_a),np.array(sequence_b)
    M,N =len(sequence_a),len(sequence_b)
    cost= np.ones((M,N))
    #  Initialize the first row and column
    cost[0,0]= distance_func(sequence_a[0],sequence_b[0])
    for i in range(1, M):
        cost[i, 0]=cost[i - 1, 0]+distance_func(sequence_a[i],sequence_b[0])

    for j in range(1, N):
        cost[0, j] = cost[0, j - 1] + distance_func(sequence_a[0], sequence_b[j])

    #  Populate rest of cost matrix within window
    for i in range(1, M):
        for j in range(max(1, i - mww), min(N, i +mww)):
            choices = cost[i - 1, j - 1], cost[i,j - 1], cost[i - 1, j]
            cost[i, j] =min(choices) + distance_func(sequence_a[i],sequence_b[j])

    #  Return DTW distance given window 
    return cost[-1, -1]
